<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<META http-equiv="Content-Type" content="text/html; charset=UTF-8">
<link rel="stylesheet" href="../../../style.css" type="text/css" media="screen">
<link rel="stylesheet" href="../../../print.css" type="text/css" media="print">
<meta content="BinarySearchTree,de.polygonal.ds.BinarySearchTree,root,size,clear,contains,dump,find,getIterator,insert,isEmpty,remove,toArray,toString" name="keywords">
<title>de.polygonal.ds.BinarySearchTree</title>
</head>
<body>
<script type="text/javascript" language="javascript" src="../../../asdoc.js"></script><script type="text/javascript" language="javascript" src="../../../cookies.js"></script><script type="text/javascript" language="javascript">
<!--
				asdocTitle = 'BinarySearchTree - AS3 Data Structures For Game Developers';
				var baseRef = '../../../';
				window.onload = configPage;
			--></script>
<table style="display:none" id="titleTable" cellspacing="0" cellpadding="0" class="titleTable">
<tr>
<td align="left" class="titleTableTitle">AS3 Data Structures For Game Developers v1.04</td><td align="right" class="titleTableTopNav"><a onclick="loadClassListFrame('../../../all-classes.html')" href="../../../package-summary.html">All&nbsp;Packages</a>&nbsp;|&nbsp;<a onclick="loadClassListFrame('../../../all-classes.html')" href="../../../class-summary.html">All&nbsp;Classes</a>&nbsp;|&nbsp;<a onclick="loadClassListFrame('../../../index-list.html')" href="../../../all-index-A.html">Index</a>&nbsp;|&nbsp;<a href="../../../index.html?de/polygonal/ds/BinarySearchTree.html&amp;de/polygonal/ds/class-list.html" id="framesLink1">Frames</a><a onclick="parent.location=document.location" href="" style="display:none" id="noFramesLink1">No&nbsp;Frames</a></td><td rowspan="3" align="right" class="titleTableLogo"><img alt="Adobe Logo" title="Adobe Logo" class="logoImage" src="../../../images/logo.jpg"></td>
</tr>
<tr class="titleTableRow2">
<td align="left" id="subTitle" class="titleTableSubTitle">Class&nbsp;BinarySearchTree</td><td align="right" id="subNav" class="titleTableSubNav"><a href="#propertySummary">Properties</a>&nbsp;| <a href="#methodSummary">Methods</a></td>
</tr>
<tr class="titleTableRow3">
<td colspan="2">&nbsp;</td>
</tr>
</table>
<script type="text/javascript" language="javascript">
<!--
if (!isEclipse() || window.name != ECLIPSE_FRAME_NAME) {titleBar_setSubTitle("Class BinarySearchTree"); titleBar_setSubNav(false,true,false,false,false,false,true,false,false,false,false,false,false,false);}
--></script>
<div class="MainContent">
<table cellspacing="0" cellpadding="0" class="classHeaderTable">
<tr>
<td class="classHeaderTableLabel">Package</td><td><a onclick="javascript:loadClassListFrame('class-list.html')" href="package-detail.html">de.polygonal.ds</a></td>
</tr>
<tr>
<td class="classHeaderTableLabel">Class</td><td class="classSignature">public class BinarySearchTree</td>
</tr>
<tr>
<td class="classHeaderTableLabel">Implements</td><td><a href="Collection.html">Collection</a></td>
</tr>
</table>
<p></p>
  A Binary Search Tree (BST).
  
  A BST stores data in a recursive manner so that you can access it quickly
  by using a key. Therefore, a BST automatically sorts data as it is
  inserted. For a BST to be valid, every node has to follow two rules:
  <ol><li>The data value in the left subtree must be less than the data
  value in the current node.</li><li>The data value in the right subtree
  must be greater than the data value in the current node.</li></ol> 
  <p></p>
<br>
<hr>
</div>
<a name="propertySummary"></a>
<div class="summarySection">
<div class="summaryTableTitle">Public Properties</div>
<table id="summaryTableProperty" class="summaryTable " cellpadding="3" cellspacing="0">
<tr>
<th>&nbsp;</th><th colspan="2">Property</th><th class="summaryTableOwnerCol">Defined&nbsp;by</th>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol"><a class="signatureLink" href="#root">root</a> : <a href="../ds/BinaryTreeNode.html">BinaryTreeNode</a>
<div class="summaryTableDescription">
   The root node being referenced.</div>
</td><td class="summaryTableOwnerCol">BinarySearchTree</td>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol"><a class="signatureLink" href="#size">size</a> : int<div class="summaryTableDescription">[read-only]
   
   The total number of items.</div>
</td><td class="summaryTableOwnerCol">BinarySearchTree</td>
</tr>
</table>
</div>
<a name="methodSummary"></a>
<div class="summarySection">
<div class="summaryTableTitle">Public Methods</div>
<table id="summaryTableMethod" class="summaryTable " cellpadding="3" cellspacing="0">
<tr>
<th>&nbsp;</th><th colspan="2">Method</th><th class="summaryTableOwnerCol">Defined&nbsp;by</th>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol">
<div class="summarySignature">
<a class="signatureLink" href="#BinarySearchTree()">BinarySearchTree</a>(compare:Function = null)</div>
<div class="summaryTableDescription">
   Initializes a BST tree with a given comparison function.</div>
</td><td class="summaryTableOwnerCol">BinarySearchTree</td>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol">
<div class="summarySignature">
<a class="signatureLink" href="#clear()">clear</a>():void</div>
<div class="summaryTableDescription">
   The tree is cleared recursively, starting from the node on which the
   method is called.</div>
</td><td class="summaryTableOwnerCol">BinarySearchTree</td>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol">
<div class="summarySignature">
<a class="signatureLink" href="#contains()">contains</a>(obj:*):Boolean</div>
<div class="summaryTableDescription">
   
   Determines if the collection contains a given item.</div>
</td><td class="summaryTableOwnerCol">BinarySearchTree</td>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol">
<div class="summarySignature">
<a class="signatureLink" href="#dump()">dump</a>():String</div>
<div class="summaryTableDescription">
   Prints out all elements (for debug/demo purposes).</div>
</td><td class="summaryTableOwnerCol">BinarySearchTree</td>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol">
<div class="summarySignature">
<a class="signatureLink" href="#find()">find</a>(obj:*):<a href="../ds/BinaryTreeNode.html">BinaryTreeNode</a>
</div>
<div class="summaryTableDescription">
   Finds a piece of data in the tree and returns a reference to the node
   that contains a match, or null if no match is found.</div>
</td><td class="summaryTableOwnerCol">BinarySearchTree</td>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol">
<div class="summarySignature">
<a class="signatureLink" href="#getIterator()">getIterator</a>():<a href="../ds/Iterator.html">Iterator</a>
</div>
<div class="summaryTableDescription">
   An iterator is not supported, use BinaryTreeNode.preorder(),
   inorder() and postorder() instead.</div>
</td><td class="summaryTableOwnerCol">BinarySearchTree</td>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol">
<div class="summarySignature">
<a class="signatureLink" href="#insert()">insert</a>(obj:*):void</div>
<div class="summaryTableDescription">
   Inserts an item into the tree.</div>
</td><td class="summaryTableOwnerCol">BinarySearchTree</td>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol">
<div class="summarySignature">
<a class="signatureLink" href="#isEmpty()">isEmpty</a>():Boolean</div>
<div class="summaryTableDescription">
   
   Checks if the collection is empty.</div>
</td><td class="summaryTableOwnerCol">BinarySearchTree</td>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol">
<div class="summarySignature">
<a class="signatureLink" href="#remove()">remove</a>(node:<a href="BinaryTreeNode.html">BinaryTreeNode</a>):void</div>
<div class="summaryTableDescription">
   Removes a node from the BST.</div>
</td><td class="summaryTableOwnerCol">BinarySearchTree</td>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol">
<div class="summarySignature">
<a class="signatureLink" href="#toArray()">toArray</a>():Array</div>
<div class="summaryTableDescription">
   
   Converts the collection into an array.</div>
</td><td class="summaryTableOwnerCol">BinarySearchTree</td>
</tr>
<tr class="">
<td class="summaryTablePaddingCol">&nbsp;</td><td class="summaryTableInheritanceCol">&nbsp;</td><td class="summaryTableSignatureCol">
<div class="summarySignature">
<a class="signatureLink" href="#toString()">toString</a>():String</div>
<div class="summaryTableDescription">
   Prints out a string representing the current object.</div>
</td><td class="summaryTableOwnerCol">BinarySearchTree</td>
</tr>
</table>
</div>
<script type="text/javascript" language="javascript">
<!--
showHideInherited();
--></script>
<div class="MainContent">
<a name="propertyDetail"></a>
<div class="detailSectionHeader">Property detail</div>
<a name="root"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">root</td><td class="detailHeaderType">property</td>
</tr>
</table>
<div class="detailBody">
<code>public var root:<a href="../ds/BinaryTreeNode.html">BinaryTreeNode</a></code><p>
   The root node being referenced.
   </p></div>
<a name="size"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">size</td><td class="detailHeaderType">property</td><td class="detailHeaderRule">&nbsp;</td>
</tr>
</table>
<div class="detailBody">
<code>size:int</code>&nbsp;&nbsp;[read-only]<p>
   
   The total number of items.
   
   </p><span class="label">Implementation</span>
<br>
<code>&nbsp;&nbsp;&nbsp;&nbsp;public function get size():int</code>
<br>
</div>
<a name="constructorDetail"></a>
<div class="detailSectionHeader">Constructor detail</div>
<a name="BinarySearchTree()"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">BinarySearchTree</td><td class="detailHeaderParens">()</td><td class="detailHeaderType">constructor</td>
</tr>
</table>
<div class="detailBody">
<code>public function BinarySearchTree(compare:Function = null)</code><p>
   Initializes a BST tree with a given comparison function. The function
   should return -1 if the left is 'less than' the right, 0 if they are
   equal, and 1 if the left is 'greater than' the right. If the function
   is omitted, the BST uses a default function for comparing integers.
   
   </p><span class="label">Parameters</span>
<table border="0" cellspacing="0" cellpadding="0">
<tr>
<td width="20px"></td><td><code><span class="label">compare</span>:Function</code> (default = <code>null</code>)<code></code> &mdash; The comparison function.
   </td>
</tr>
</table>
</div>
<a name="methodDetail"></a>
<div class="detailSectionHeader">Method detail</div>
<a name="clear()"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">clear</td><td class="detailHeaderParens">()</td><td class="detailHeaderType">method</td>
</tr>
</table>
<div class="detailBody">
<code>public function clear():void</code><p>
   The tree is cleared recursively, starting from the node on which the
   method is called.
   
   </p><p>
   Clears all items.
   </p></div>
<a name="contains()"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">contains</td><td class="detailHeaderParens">()</td><td class="detailHeaderType">method</td><td class="detailHeaderRule">&nbsp;</td>
</tr>
</table>
<div class="detailBody">
<code>public function contains(obj:*):Boolean</code><p>
   
   Determines if the collection contains a given item.
   
   </p><span class="label">Parameters</span>
<table border="0" cellspacing="0" cellpadding="0">
<tr>
<td width="20px"></td><td><code><span class="label">obj</span>:*</code> &mdash; The item to search for.
   
   </td>
</tr>
</table>
<p></p>
<span class="label">Returns</span>
<table border="0" cellspacing="0" cellpadding="0">
<tr>
<td width="20"></td><td><code>Boolean</code> &mdash; True if the item exists, otherwise false.
   </td>
</tr>
</table>
</div>
<a name="dump()"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">dump</td><td class="detailHeaderParens">()</td><td class="detailHeaderType">method</td><td class="detailHeaderRule">&nbsp;</td>
</tr>
</table>
<div class="detailBody">
<code>public function dump():String</code><p>
   Prints out all elements (for debug/demo purposes).
   
   </p><p></p>
<span class="label">Returns</span>
<table border="0" cellspacing="0" cellpadding="0">
<tr>
<td width="20"></td><td><code>String</code> &mdash; A human-readable representation of the structure.
   </td>
</tr>
</table>
</div>
<a name="find()"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">find</td><td class="detailHeaderParens">()</td><td class="detailHeaderType">method</td><td class="detailHeaderRule">&nbsp;</td>
</tr>
</table>
<div class="detailBody">
<code>public function find(obj:*):<a href="../ds/BinaryTreeNode.html">BinaryTreeNode</a></code><p>
   Finds a piece of data in the tree and returns a reference to the node
   that contains a match, or null if no match is found.
   
   </p><span class="label">Parameters</span>
<table border="0" cellspacing="0" cellpadding="0">
<tr>
<td width="20px"></td><td><code><span class="label">obj</span>:*</code> &mdash; The data to find.
   
   </td>
</tr>
</table>
<p></p>
<span class="label">Returns</span>
<table border="0" cellspacing="0" cellpadding="0">
<tr>
<td width="20"></td><td><code><a href="../ds/BinaryTreeNode.html">BinaryTreeNode</a></code> &mdash; 
                        A node containing the data or null if the data wasn't found.
   
                        
                     </td>
</tr>
</table>
</div>
<a name="getIterator()"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">getIterator</td><td class="detailHeaderParens">()</td><td class="detailHeaderType">method</td><td class="detailHeaderRule">&nbsp;</td>
</tr>
</table>
<div class="detailBody">
<code>public function getIterator():<a href="../ds/Iterator.html">Iterator</a></code><p>
   An iterator is not supported, use BinaryTreeNode.preorder(),
   inorder() and postorder() instead.
   
   </p><p></p>
<span class="label">Returns</span>
<table border="0" cellspacing="0" cellpadding="0">
<tr>
<td width="20"></td><td><code><a href="../ds/Iterator.html">Iterator</a></code></td>
</tr>
</table>
<p>
<span class="label">See also</span>
</p>
<div class="seeAlso">
<a href="BinaryTreeNode.html#preorder" target="">BinaryTreeNode.preorder</a>
<br>
<a href="BinaryTreeNode.html#inorder" target="">BinaryTreeNode.inorder</a>
<br>
<a href="BinaryTreeNode.html#postorder" target="">BinaryTreeNode.postorder</a>
</div>
</div>
<a name="insert()"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">insert</td><td class="detailHeaderParens">()</td><td class="detailHeaderType">method</td><td class="detailHeaderRule">&nbsp;</td>
</tr>
</table>
<div class="detailBody">
<code>public function insert(obj:*):void</code><p>
   Inserts an item into the tree.
   
   </p><span class="label">Parameters</span>
<table border="0" cellspacing="0" cellpadding="0">
<tr>
<td width="20px"></td><td><code><span class="label">obj</span>:*</code> &mdash; The data.
   </td>
</tr>
</table>
</div>
<a name="isEmpty()"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">isEmpty</td><td class="detailHeaderParens">()</td><td class="detailHeaderType">method</td><td class="detailHeaderRule">&nbsp;</td>
</tr>
</table>
<div class="detailBody">
<code>public function isEmpty():Boolean</code><p>
   
   Checks if the collection is empty.
   
   </p><p></p>
<span class="label">Returns</span>
<table border="0" cellspacing="0" cellpadding="0">
<tr>
<td width="20"></td><td><code>Boolean</code> &mdash; True if empty, otherwise false.
   </td>
</tr>
</table>
</div>
<a name="remove()"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">remove</td><td class="detailHeaderParens">()</td><td class="detailHeaderType">method</td><td class="detailHeaderRule">&nbsp;</td>
</tr>
</table>
<div class="detailBody">
<code>public function remove(node:<a href="BinaryTreeNode.html">BinaryTreeNode</a>):void</code><p>
   Removes a node from the BST.
      </p><span class="label">Parameters</span>
<table border="0" cellspacing="0" cellpadding="0">
<tr>
<td width="20px"></td><td><code><span class="label">node</span>:<a href="BinaryTreeNode.html">BinaryTreeNode</a></code> &mdash; The node to remove.
   </td>
</tr>
</table>
</div>
<a name="toArray()"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">toArray</td><td class="detailHeaderParens">()</td><td class="detailHeaderType">method</td><td class="detailHeaderRule">&nbsp;</td>
</tr>
</table>
<div class="detailBody">
<code>public function toArray():Array</code><p>
   
   Converts the collection into an array.
   
   </p><p></p>
<span class="label">Returns</span>
<table border="0" cellspacing="0" cellpadding="0">
<tr>
<td width="20"></td><td><code>Array</code> &mdash; An array.
   </td>
</tr>
</table>
</div>
<a name="toString()"></a>
<table cellspacing="0" cellpadding="0" class="detailHeader">
<tr>
<td class="detailHeaderName">toString</td><td class="detailHeaderParens">()</td><td class="detailHeaderType">method</td><td class="detailHeaderRule">&nbsp;</td>
</tr>
</table>
<div class="detailBody">
<code>public function toString():String</code><p>
   Prints out a string representing the current object.
   
   </p><p></p>
<span class="label">Returns</span>
<table border="0" cellspacing="0" cellpadding="0">
<tr>
<td width="20"></td><td><code>String</code> &mdash; A string representing the current object.
   </td>
</tr>
</table>
</div>
<br>
<br>
<hr>
<br>
<p></p>
<center class="copyright">Copyright 2007-2008 Michael Baczynski | POLYGONAL</center>
</div>
</body>
</html>
<!--Copyright 2007-2008 Michael Baczynski | POLYGONAL-->
